package com.heima.leetcode.datastructure.binarysearchtree;

import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * <strong>二叉搜索树范围求和 938</strong>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/12 10:27
 */
public class RangeSumBST {

    /**
     * <h3>方法一：非递归中序遍历比较</h3>
     * @param root 树的根节点
     * @param low 节点值的下界（包含）
     * @param high 节点值的上界（包含）
     * @return 满足条件的节点值得累加值
     */
    public static int rangeSumBST1(TreeNode root, int low, int high) {
        TreeNode curr = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int sum = 0;
        while (curr != null || !stack.isEmpty()){
            if (curr != null){
                stack.push(curr);
                curr = curr.left;
            }else {
                TreeNode last = stack.pop();
                if (last.val >= low && last.val <= high){
                    sum += last.val;
                }else if (last.val > high){
                    break;
                }
                curr = last.right;
            }
        }
        return sum;
    }

    /**
     * <h3>方法二：用上下界递归实现，性能最好</h3>
     * @param root 当前树的根节点
     * @param low 下界（包含）
     * @param high 上界（包含）
     * @return 范围求和结果
     */
    public static int rangeSumBST2(TreeNode root, int low, int high){
        // 递的时候计算当前树的左子树的范围求和结果和右子树的范围求和结果，并和当前树的根节点值累加
        if (root == null){
            return 0;
        }
        if (root.val >= low && root.val <= high){
            return rangeSumBST2(root.left, low, high) + rangeSumBST2(root.right, low, high) + root.val;
        }else if (root.val < low){ // 当前树根节点在范围左边，则只用找右子树，剪枝
            return rangeSumBST2(root.right, low, high);
        }else { // 当前树根节点在范围右边，则只用找左子树，剪枝
            return rangeSumBST2(root.left, low, high);
        }
    }

    /**
     * <h3>方法三：递归中序遍历比较</h3>
     * @param root 当前树头节点
     * @param low 上界
     * @param high 下界
     * @return 当前树满足要求的节点值之和
     */
    public static int rangeSumBST3(TreeNode root, int low, int high){
        AtomicInteger sum = new AtomicInteger(0);
        rangeSum(root,low,high,sum);
        return sum.get();
    }

    /**
     * 方法三的递归实现
     * @param root 当前树的根节点
     * @param low 下界
     * @param high 上界
     * @param sum 存放sum的对象，确保同一份对象，可改变对象，修改对象内部的值，而不是修改它的引用
     */
    private static void rangeSum(TreeNode root, int low, int high, AtomicInteger sum){
        if (root == null){
            return;
        }
        rangeSum(root.left, low, high, sum);
        if (root.val >= low && root.val <= high){
            sum.set(sum.get() + root.val);
        }
        if (root.val > high){
            return;
        }
        rangeSum(root.right, low, high, sum);
    }
}
